// 1789. [java合并区间]简易内存池.中  https://oj.rnd.huawei.com/problems/1789/details
// https://www.online1987.com/%E7%AE%80%E6%98%93%E5%86%85%E5%AD%98%E6%B1%A0/
// 请实现一个简易内存池,根据请求命令完成内存分配和释放。
// 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
// REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
// RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
// 1.内存池总大小为100字节。
// 2.内存池地址分配必须是连续内存，并优先从低地址分配。
// 3.内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
// 4.不会释放已申请的内存块的中间地址。
// 5.释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
// 输入 5
// REQUEST=10
// REQUEST=20
// RELEASE=0
// REQUEST=20
// REQUEST=10
// 输出 0
// 10
// 30
// 0
public static final int POOL_SIZE = 100;
SortedMap<Integer, Integer> allocated = new TreeMap<>();
// 返回分配的内存首地址(string)，失败返回字符串 "error"
String request(int size) {
    // 在此补充你的代码
    if (size == 0) {
        return "error";
    }
    if (allocated.isEmpty()) {
        if (size <= POOL_SIZE) {
            allocated.put(0, size - 1);
            return "0";
        } else {
            return "error";
        }
    }
    Map.Entry<Integer, Integer>[] entryArray = allocated.entrySet().toArray(new Map.Entry[0]);
    for (int i = 0; i < entryArray.length; i++) {
        if (i == 0 && entryArray[i].getKey() >= size) {
            allocated.put(0, size - 1);
            return "0";
        } else if (i == entryArray.length - 1 && POOL_SIZE - 1 - entryArray[i].getValue() >= size) {
            allocated.put(entryArray[i].getValue() + 1, entryArray[i].getValue() + size);
            return String.valueOf(entryArray[i].getValue() + 1);
        } else if (i < entryArray.length - 1 && entryArray[i + 1].getKey() - 1 - entryArray[i].getValue() >= size) {
            allocated.put(entryArray[i].getValue() + 1, entryArray[i].getValue() + size);
            return String.valueOf(entryArray[i].getValue() + 1);
        }
    }
    return "error";
}

// 成功返回 true；失败返回 false，失败时框架会自动输出 "error"
boolean release(int startAddress) {
    if (allocated.containsKey(startAddress)) {
        allocated.remove(startAddress);
        return true;
    }
    return false;
}

